package algorithm.minitree;

import java.util.Vector;

/**
 * @author bingo
 * @Description    最小生成树-------->KruskalMst 算法   不断寻找最小边
 * @Date 2018/4/21
 */
public class KruskalMST<Weight extends Number & Comparable > {

    /**图的引用*/
    private  WeightedGraph<Weight> G;
    /**最小堆*/
    private MinHeap<Edge<Weight>> minHeap;
    /**生成最小树所有的边*/
    private Vector<Edge<Weight>> mst;
    /**最小生成树的权值*/
    private Number mstWeight;

    public KruskalMST(WeightedGraph<Weight> g) {
        G = g;
        mst = new Vector<>();
        this.minHeap = new MinHeap<>(G.E());
        System.out.println("堆大小:"+minHeap.size());

        /**将图中的所有边存放到一个最小堆中*/
        for(int i=0;i<G.V();i++){
            for(Edge<Weight> e : g.adj(i)){
               if(i<e.getOther(i)){
                   minHeap.insert(e);
            }
          }

        }
        /** 创建一个并查集, 来查看已经访问的节点的联通情况，如果是联通的必然会构成一个环*/
        UnionFind unionFind = new UnionFind(G.V());
        while (!minHeap.isEmpty()&& mst.size() < g.V() - 1 ){
            Edge<Weight> e = minHeap.pop();
            if(unionFind.isConnected(e.a(),e.b())){
                continue;
            }
            mst.add(e);

            unionFind.unionElements(e.a(),e.b());
        }
        mstWeight = mst.get(0).wt();

        for(int i=1;i<mst.size();i++){
            mstWeight  =  mstWeight.doubleValue() + mst.get(i).wt().doubleValue();
        }


        }
      /**返回构成最小生成树边的集合*/
    public Vector<Edge<Weight>> getMst(){

        return  mst;
    }

    /***返回最小生成树的权值*/
    public Number getMstWeight(){

        return  mstWeight;
    }
}
